This application pertains to the field of communications generally, and in particular to communication networks which interconnect a plurality of user stations and share a common resource. Specifically, it pertains to the allocation and scheduling of processor in a multi-queue system in which the service capabilities of the processor are shared by the various queues in the system, the queues having heterogeneous types of tasks with differing priorities, such as the allocation of real time operation of a data processor in a large telephone switching center, or the allocation of bandwidth of the bus of a local area network.
Communication networks range in scope from small local area networks connecting a few telephones or personal computers to the world-wide public switched telephone network. Regardless of size, as networks increase in complexity more sophisticated resource allocation policies become necessary. The allocation of a single resource to many requests for its use is critical to the central processor in a network switch. The result of the resource allocation scheme must be the optimization of a projected cost function. Similar concerns affect comparable resource allocation schemes for smaller networks, in which performance improvement or system optimization yields an improvement in a projected cost function.
The present invention is concerned primarily with networks under the control of a processor unit, usually a digital computer, having heterogeneous traffic, tasks or requests for service. Specifically, it is concerned with one aspect of the task profile, namely the priority assigned to each type of task, and the measure of system performance for that aspect, namely the response time or average mean delay of service for tasks in each queue. In a network having heterogeneous classes of traffic with multiple priorities, there is a danger that high priority traffic will continually preempt lower priority traffic, leading to the situation in which the low priority traffic is served after an inordinately long delay.
An example is the allocation of a processor's time within a large switch. Such systems may be modeled by a server, representing the processor, attending to the entries of two or more queues that arrive randomly and have random service requirements, as illustrated in FIG. 1. The entries might represent voice and/or data telecommunication traffic or internal messages from one part of the processor to another. The statistical characteristics of the traffic could be quite varied: if the entries are voice circuit-switched calls, then the arrival pattern might be random and its duration random, with an average of a few minutes. On the other hand, if the entries are a digitalized data stream the inter-arrival time might be non-random and its duration much longer or much shorter than a few minutes, depending on its specific application. The scheduling problem of concern in this application is that of deciding in which order the entries should be processed in order to optimize the system's overall performance while taking into account the effects of the randomness in the system.
Hereinafter, the network traffic and other requests for processor service will be called tasks and the different classes of traffic will be called types of tasks. Different types of tasks will be said to be in different queues.
A number of resource allocation or control schemes which involve control of access to a network computer and optimization of message routing through a network have been proposed and to some extent implemented in various networks. Some of these control schemes include one or more schemes for resolution of the conflicts which can arise from multiple priorities. This aspect of the problem can be generalized to the scheduling of network resources to provide minimally adequate service to all users of a network. The prior art discloses a number of alternative techniques for scheduling the services of a network and/or its processor. Five prior art schedules are discussed in the following paragraphs.
In a communication network using an exhaustive service schedule, all customers are served from a first queue until the queue is empty before any customers are served from the next queue. Stated in other terms, for i=0, 1, 2, . . . , n-1 (where n represents the number of different tasks in a system), the processor serves type i tasks until no more are available, and then serves type (i+1) modulus (n) tasks. This schedule suffers from a number of disadvantages. It does not permit the allocation of priority among the tasks. If the queue presently being served has a very low priority, service cannot be interrupted for an incoming high priority task. Another disadvantage is that the average delay of service, i.e., waiting time, of a type i task might be severely increased when the number of type j tasks, where j.noteq.i, requiring service increases sharply. A further disadvantage is that such a schedule has no free parameters, thus does not permit real-time continuous variable control.
In a communication system using a gated schedule, all customers are served from a first queue who had arrived on that queue before service for the first customer of that queue started, and then customers on the next queue are served similarly. In other words, during each cycle, for i=0, 1, 2, . . . , n-1, (where n represents the number of different types of tasks in a system), the processor serves all of the type i tasks that arrived before the first type i task was served and then the processor serves the type (i+1) modulus (n) tasks. A gated schedule has the disadvantage that it does not permit the allocation of priorities among the tasks, and the disadvantage that it has no free parameters for real-time continuous variable control.
In a communication system using a clocked schedule, the processor serves all customers from a first queue until the queue is empty, and then proceeds to serve customers on the next queue, as it would do on an exhaustive service schedule, discussed above, except with the modification that after every time period t (where t is prespecified) the processor stops what it is doing and returns to the first queue. This type of schedule suffers from the same disadvantages as the exhaustive service schedule plus the further disadvantage that its performance cannot be analytically analyzed. Therefore some undesirable uncertainty on the part of the system designer is incurred. It also suffers the further disadvantage that the implementation of such a schedule requires that the processor store in memory information about the past activities of the system, that is, the schedule is not memoryless.
In a communication system using a limited service schedule, the processor serves up to a prespecified number of customers on a first queue, then proceeds to serve up to a prespecified number on the next queue, cycling through all the queues in the system continuously. In other words, for i=0, 1, 2, . . . , n-1, (where n represents the number of different types of tasks in a system), the processor serves up to m.sub.i type i tasks (where m.sub.i 's are prespecified integers) and then serves type (i+1) modulus (n) tasks. This type of schedule suffers from the disadvantage that it has no free parameters for real-time continuous variable control. It also suffers from the disadvantage that it cannot be analytically analyzed. And this schedule is also not memoryless.
In a communication system using a strict priority schedule, the processor serves all customers on a queue having one priority only when there are no queues of customers having a higher priority. In other words, for i=0, 1, 2, . . . , n-1, (where n represents the number of different types of tasks in a system), the processor serves type i tasks only when there are no type 1, 2, . . . i-1 tasks that need service. The strict priority schedule suffers also from the disadvantage that the average delay of service of a type i task might be severely increased when the number of type j tasks, where j&lt;i, requiring service, increases sharply. The strict priority schedule also has no free parameters to allow real-time continuous variable control.